#ifndef __LOSER_TREE_H__
#define __LOSER_TREE_H__

/*
 * - 为什么需要用败者树算法？
 * 
 * 日志输出需要按照时间排序，但是每个业务线程都有自己的ring队列，单线程队列内部
 * 的日志entry是有序的，不同业务线程之间的日志entry需要排序。多路归并排序的常用
 * 方案是败者树算法，因此，hlog也使用败者树算法来降低日志按时间排序的开销。
 * 
 * - hlog的败者树算法有什么不同？为什么？
 *
 * 对归并过程做了阶段划分，每个阶段开始的时候，遍历所有外部节点。归并过程忽略
 * 掉那些晚于本阶段遍历时刻的日志entry，这些entry放到下一个阶段中去处理。
 * 调整之后的算法比标准算法开销更大，但是开销小于每次遍历所有线程的ring查找最
 * 旧的entry，当日志输出压力很大的时候，每个阶段都积累了很多日志entry需要处理，
 * 这个开销可以忽略。当日志输出压力比较小的时候，遍历开销不影响日志输出性能。
 */

#include <assert.h>

struct loser_tree;

typedef void (*getkey_t)(int ex_idx, void **key);
typedef long (*cmpkey_t)(void *key1, void *key2);

struct loser_tree *lt_create(int nr_ex_node, int cap, getkey_t getkey,
	cmpkey_t cmpkey);
void lt_destroy(struct loser_tree *lt);
void lt_top(struct loser_tree *lt, int *index);

void lt_refresh(struct loser_tree *lt, int nr_ex_node);

void lt_adjust(struct loser_tree *lt, int _s);

int *lt_get_ls(struct loser_tree *lt);

void lt_dump(struct loser_tree *lt);

#endif //__LOSER_TREE_H__

